from typing import *


class Solution:
    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
        n = len(nums)
        idx = [v for v in range(n)]
        idx.sort(key=lambda b: nums[b])
        t = []
        ans = [0] * n
        for i in range(n):
            if i == 0 or nums[idx[i]] - nums[idx[i - 1]] <= limit:
                t.append(idx[i])
            else:
                for j, k in zip(t, sorted(t)):
                    ans[k] = nums[j]
                t = [idx[i]]
        for j, k in zip(t, sorted(t)):
            ans[k] = nums[j]
        return ans


s = Solution()
print(s.lexicographicallySmallestArray(nums=[1, 5, 3, 9, 8], limit=2))
